<!DOCTYPE html>  
<html>
    <meta charset="utf-8" />  
    <title>快速算法原理</title>  
<body>
    <h1>快速算法原理</h1>
    <p>
        1.首先，从数组中选择中间一项作为主元。
    </p>
    <p>
        2.创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。
        移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，
        然后交换它们，重复这个过程，直到左指针超过了右指针。
        这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分操作。
    </p>
    <p>
        3.接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的
        子数组）重复之前的两个步骤，直至数组已完全排序。
    </p>>
</body>
<script>  
    
    // Array.prototype.quickSort = function() {
    //     const partition = (array, left, right) => {
    //         var pivot = array[Math.floor((right + left) / 2)]
    //         // [1,3,5,2,7,0,13]
    //         let i = left
    //         let j = right
    //         while (i <= j) {
    //             while (array[i] < pivot) {
    //                 i++
    //             }
    //             while (array[j] > pivot) {
    //                 j--
    //             }
    //             console.log('ij',i,j)
    //             if (i <= j) {
    //                 let aux = array[i]
    //                 array[i] = array[j]
    //                 array[j] = aux
    //                 i++
    //                 j--
    //             }
    //             console.log('arr',arr)
    //         }
    //         return i
    //     }
    //     const quick = (array, left, right) => {
    //         let index
    //         if (array.length > 1) {
    //             index = partition(array, left, right)
    //             if (left < index - 1) {
    //                 quick(array, left, index - 1)
    //             }
    //             if (index < right) {
    //                 quick(array, index, right)
    //             }
    //         }
    //     }
    //     quick(this, 0, this.length - 1)
    //     return this
    // }
    // const arr = [1,3,5,2,7,0,13]
    // console.log(arr.quickSort())
    
    const arr = [1,3,5,2,7,0,13]
    const quickSort=function(arr){
        var length = arr.length;
        if(length<=1){
            return arr;
        }
        var pivoIndex = Math.floor(length/2);
        var pivot = arr.splice(pivoIndex,1)[0]
        var left = [];
    　　var right = [];
    　　for (var i = 0; i < arr.length; i++){
    　　　　if (arr[i] < pivot) {
    　　　　　　left.push(arr[i]);
    　　　　} else {
    　　　　　　right.push(arr[i]);
    　　　　}
    　　}
        return quickSort(left).concat([pivot], quickSort(right));
    }
    console.log(quickSort(arr))
    
</script> 
</html>